# encoding: utf-8
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: shell_sort.py 
@time: 2019/7/1 14:11
"""
'''
希尔排序是插入排序的一种更高效率的实现。它与插入排序的不同之处在于，它会优先比较距离较远的元素。
'''
def shellSort(nums):
    lens = len(nums)
    gap = 1
    while gap < lens // 3:
        gap = gap * 3 + 1
        # 动态定义间隔序列
        while gap > 0:
            for i in range(gap, lens):
                curNum, preIndex = nums[i], i - gap
                # curNum 保存当前待插入的数
                while preIndex >= 0 and curNum < nums[preIndex]:
                    nums[preIndex + gap] = nums[preIndex]
                    # 将比curNum大的元素向后移动
                    preIndex -= gap
                nums[preIndex + gap] = curNum
                # 待插入的数正确位置
            gap //= 3
            # 下一个动态间隔
        return nums

# Example use
nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
import time
starttime = time.time()
print(starttime,id(nums))
print(shellSort(nums), id(shellSort(nums)))
endtime = time.time()
print(endtime - starttime)

